package leetcode.Hot100;

/**
 * @author Cheng Jun
 * Description: 给定一个  m x n 二维字符网格  board 和一个字符串单词  word 。如果  word 存在于网格中，返回 true ；否则，返回 false 。
 * <p>
 * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
 * <p>
 * 1 <= m, n <= 6
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/word-search
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @version 1.0
 * @date 2021/12/6 16:28
 * 二刷，面试题，经典回溯
 */
public class exist {

    static boolean exitFlag = false;

    public static void main(String[] args) {
        System.out.println(exist(new char[][]{new char[]{'a'}}, "b"));
    }

    // 思路分析：复杂问题可以通过 极端情况 观察规律，1 x n 的 二维网格，可以看做一维数组中 有没有 word，某个位置的前后都能作为候选项。
    // 但是因为同一单元格的字母不能重复使用，所以要记录 数组中被选择的下标。
    static boolean exist(char[][] board, String word) {
        char[] wordChar = word.toCharArray();
        boolean[][] used = new boolean[board.length][board[0].length];
        if (wordChar.length > board.length * board[0].length) {
            return false;
        }
        outer:
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (exitFlag) {
                    break outer;
                }
                if (wordChar[0] == board[i][j]) {
                    used[i][j] = true;
                    if (wordChar.length > 1) {
                        backTrack(i, j, used, board, wordChar, 1);
                    } else {
                        exitFlag = true;
                    }
                    used[i][j] = false;
                }
            }
        }
        return exitFlag;
    }

    static void backTrack(int row, int column, boolean[][] used, char[][] board, char[] wordChar, int findIndex) {
        // 如果已经找到，快速终止 待回溯的路径
        if (exitFlag) {
            return;
        }

        // 顺时针，从 board[i][j] 开始，相邻单元格按照上、右、下、左 的顺序查找
        // 上相邻的单元格有效，且没有被使用，且等于 wordChar[findIndex]
        if (row - 1 >= 0 && !used[row - 1][column] && board[row - 1][column] == wordChar[findIndex]) {
            if (findIndex == wordChar.length - 1) {
                exitFlag = true;
                return;
            }
            used[row - 1][column] = true;
            backTrack(row - 1, column, used, board, wordChar, findIndex + 1);
            used[row - 1][column] = false;
        }

        // 右相邻的单元格有效，且没有被使用，且等于 wordChar[findIndex]
        if (column + 1 < board[0].length && !used[row][column + 1] && board[row][column + 1] == wordChar[findIndex]) {
            if (findIndex == wordChar.length - 1) {
                exitFlag = true;
                return;
            }
            used[row][column + 1] = true;
            backTrack(row, column + 1, used, board, wordChar, findIndex + 1);
            used[row][column + 1] = false;
        }
        // 下相邻的单元格有效，且没有被使用，且等于 wordChar[findIndex]
        if (row + 1 < board.length && !used[row + 1][column] && board[row + 1][column] == wordChar[findIndex]) {
            if (findIndex == wordChar.length - 1) {
                exitFlag = true;
                return;
            }
            used[row + 1][column] = true;
            backTrack(row + 1, column, used, board, wordChar, findIndex + 1);
            used[row + 1][column] = false;
        }
        // 左相邻的单元格有效，且没有被使用，且等于 wordChar[findIndex]
        if (column - 1 >= 0 && !used[row][column - 1] && board[row][column - 1] == wordChar[findIndex]) {
            if (findIndex == wordChar.length - 1) {
                exitFlag = true;
                return;
            }
            used[row][column - 1] = true;
            backTrack(row, column - 1, used, board, wordChar, findIndex + 1);
            used[row][column - 1] = false;
        }
        used[row][column] = false;
    }

    static int row = 0;
    static int col = 0;

    static boolean exist1(char[][] board, String word) {
        row = board.length;
        col = board[0].length;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (board[i][j] == word.charAt(0) && backTrace1(i, j, board, word, 0)) return true;
            }
        }
        return false;
    }

    static boolean backTrace1(int rowIndex, int colIndex, char[][] board, String word, int wordIndex) {
        if (rowIndex < 0 || rowIndex >= row || colIndex < 0 || colIndex >= col || board[rowIndex][colIndex] != word.charAt(wordIndex))
            return false;
        if (wordIndex == word.length() - 1)
            return true;
        // 设置该位置为 '', 表示该位置被用过
        board[rowIndex][colIndex] = '\u0000';
        // 顺时针，上右下左
        boolean res = backTrace1(rowIndex - 1, colIndex, board, word, wordIndex + 1) ||
                backTrace1(rowIndex, colIndex + 1, board, word, wordIndex + 1) ||
                backTrace1(rowIndex + 1, colIndex, board, word, wordIndex + 1) ||
                backTrace1(rowIndex, colIndex - 1, board, word, wordIndex + 1);
        board[rowIndex][colIndex] = word.charAt(wordIndex);
        return res;
    }
}
